package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/7/7 22:14
 * @description：https://leetcode-cn.com/problems/count-good-meals/
 */
public class 大餐计数 {
    @Test
    public void test() {
        Solution solution = new Solution();
        int[] arr = {1,3,5,7,9};
        int i = solution.countPairs(arr);
        System.out.println(i);
    }

    class Solution {
        public int countPairs(int[] deliciousness) {
            final int MOD = 1000000007;
            int maxVal = Arrays.stream(deliciousness).max().getAsInt();
            int maxNum = maxVal * 2;
            int pairs = 0;
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < deliciousness.length; i++) {
                int val = deliciousness[i];
                for (int sum = 1; sum <= maxNum; sum <<= 1) {
                    int count = map.getOrDefault(sum - val, 0);
                    pairs = (pairs + count) % MOD;
                }
                map.put(val, map.getOrDefault(val, 0) + 1);
            }
            return pairs;
        }
    }


}
